package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-28 15:55
 */
public class Test17 {
    public static void main(String[] args) {
        System.out.println(new Test17().firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(new Test17().firstMissingPositive(new int[]{3, 4, -1, 1}));
        System.out.println(new Test17().firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
    }

    /**
     * 尝试改进?
     *
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }

        for (int i = 0; i < nums.length; i++) {

            if (Math.abs(nums[i]) < len + 1) {
                int temp = Math.abs(nums[i]) - 1;
                if (nums[temp] >= 0) {
                    nums[temp] *= -1;
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;
    }

//    /**
//     * 哈希表方法
//     * 通过
//     *
//     * @param nums
//     * @return
//     */
//    public int firstMissingPositive(int[] nums) {
//        HashMap<Integer, Integer> hashMap = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            hashMap.put(nums[i], 1);
//        }
//        int k = 1;
//        while (true) {
//            if (hashMap.containsKey(k)) {
//                k++;
//            } else {
//                break;
//            }
//        }
//        return k;
//    }

}
